#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int maxProfit(vector<int> &prices) {

    /*

      类似于前缀和
      区间数据
      diff array

     暴力法：二维数组，将某一天到另外一天的数据
     归纳与演绎

     假定某个答案是正确的，然后证明他。

     正确的答案一定符合某种规则，我们需要去寻找她。
     */

    int length = prices.size();

    if (length < 2) {
      return 0;
    }
    vector<int> diffs;
    diffs.push_back(0);
    for (int i = 1; i < length; i++) {
      int sub = prices[i] - prices[i - 1];
      diffs.push_back(sub);
    }
    int sum = 0;
    int max_val = 0;
    for (int i = 1; i < diffs.size(); i++) {
      sum += diffs[i];
      if (sum <= 0) {
        sum = 0;
      }
      if (sum > max_val) {
        max_val = sum;
      }
    }

    return max_val;
  }
};

int main() { return 0; }
